package a04_字符串;

import java.util.Arrays;

/**
 * <p>
 * a06_实现strStr
 * kmp算法
 * aabaabaaf
 * aabaaf
 * 发现aabaaf和aabaab不匹配直接跳到了aab的b之后开始匹配
 *
 * aabaaf的前缀
 * a
 * aa
 * aab
 * aaba
 * aabaa
 *
 * aabaaf的后缀
 * f
 * af
 * aaf
 * baaf
 * abaaf
 *
 * 求最长相等前后缀
 * a   0
 * aa  1
 * aab 0
 * aaba 1
 * aabaa 2
 * aabaaf 0
 *
 * aabaaf的前缀表就是
 * 010120
 *
 * 开始比较
 * aabaabaaf
 * aabaaf
 * 010120
 *
 * 发现f不匹配
 * 前面子串的最长相等前后缀为2
 * 说明这里有一个aa，前面也有一个aa
 * 我们在后面的aa的后面的f不匹配了
 * 我们就得从前面的aa后面的b开始匹配，下标刚好就是2
 *
 * 此时这样开始匹配
 * aabaabaaf
 * aa   baaf
 * </p>
 *
 * @author flyduck
 * @since 2024-07-11
 */
public class a06_实现strStr复习3 {

    //aabaabaaf
    //aabaaf

    //hello
    //ll
    public static void main(String[] args) {

//        System.out.println(strStr("leetcode", "leeto"));
//        System.out.println(strStr("hello", "ll"));
//        System.out.println(strStr("leetcode", "leeto"));
        System.out.println(strStr("a", "a"));

//        String str = "abbaabaaf";
        //a   b  b  a  a  b  a  a  f
        //-1, 0, 0, 0, 1, 1, 2, 1, 1
//        int[] nextArray = new int[str.length()];
//        getNextArray(nextArray,str);
//        System.out.println(Arrays.toString(str.toCharArray()));
//        System.out.println(Arrays.toString(nextArray));

        String str = "aabaab";
        int[] nextArray = getNextArray(str.toCharArray());
        System.out.println(Arrays.toString(nextArray));
    }


    //aabaabaaf
    //aabaaf
    //aaa b aaa  ba
    //           3

    public static int strStr(String haystack, String needle) {
        char[] haystackArray = haystack.toCharArray();
        char[] needleArray = needle.toCharArray();
        int[] nextArray = getNextArray(needleArray);

        int haystackIdx = 0;
        int needleIdx = 0;
        while (haystackIdx < haystackArray.length && needleIdx < needleArray.length) {
            if(haystackArray[haystackIdx] == needleArray[needleIdx]){
                haystackIdx++;
                needleIdx++;
            }else {
                needleIdx = nextArray[needleIdx];
                if(needleIdx == -1){
                    haystackIdx++;
                    needleIdx = 0;
                }
            }
        }

        if(needleIdx == needleArray.length){
            return haystackIdx - needleIdx;
        }else {
            return -1;
        }
    }

    public static int[] getNextArray(char[] chars){
        if (chars.length == 1) {
            int[] nextArray = new int[1];
            nextArray[0] = -1;
            return nextArray;
        }

        int[] nextArray = new int[chars.length];
        nextArray[0] = -1;
        nextArray[1] = 0;
        int currentIdx = 2;
        int compareIdx = nextArray[currentIdx - 1];
        while (currentIdx < nextArray.length) {
            if(chars[compareIdx] == chars[currentIdx - 1]){
                nextArray[currentIdx] = compareIdx + 1;
                currentIdx++;
                compareIdx = nextArray[currentIdx - 1];
            }else {
                if(compareIdx == 0){
                    nextArray[currentIdx] = 0;
                    currentIdx++;
                    compareIdx = nextArray[currentIdx - 1];
                }else {
                    compareIdx = nextArray[compareIdx];
                }
            }
        }

        return nextArray;

    }





}
